Informationsgehalt
Python-Implementierung
huffman.py
def count(e,L):
"""
gibt die Haeufigkeit des Vorkommens des Elements e in der Liste L zurueck
"""
return len([y for y in L if e==y])
def sort2(T):
"""
sortiert die Liste T von 2-Tupeln nach der zweiten Komponente
"""
if len(T) T[0][1]]) + \
[T[0]] + \
sort2([t for t in T[1:] if t[1] 1:
b = b[:-2]+[((b[-2],b[-1]),b[-2][1]+b[-1][1])]
b = sort2(b)
return b
def codetab(s):
"""
gibt zu einem String s die Code-Tabelle zurueck
"""
code = {} # Dictionary
t = htree(s)[0] # Baum besteht nur aus einem Tupel
c = '' # Code
stack = [(t,c)] # Teilbaum und Teilcode auf Stack legen
while len(stack) > 0:
t = stack[-1][0]
c = stack[-1][1]
stack = stack[:-1]
if type(t[0]) == str:
code.update({t[0]:c})
else:
stack = stack+[(t[0][0],c+'0')]
stack = stack+[(t[0][1],c+'1')]
return code
def encode(s,codetab):
"""
codiert einen String s mit der Codetabelle codetab
"""
code = ''
for ch in s:
code = code+codetab[ch]
return code
def decode(code,codetab):
"""
decodiert den code mit Hilfe der Codetabelle codetab
"""
s = ''
while len(code) > 0:
for ch in codetab:
wert = codetab[ch]
n = len(wert)
if wert == code[:n]:
s = s + ch
code = code[n:]
break
return s
Beispiele
>>> s = 'Das ist ein kleiner Test!'
>>> len(s)
25
>>> 25*8
200
>>> T = codetab(s)
>>> T
{'a': '1011', ' ': '11', 'e': '000', 'D': '10100', 'i': '011', 'k': '10101', 'l': '00110',
'n': '0100', 's': '100', 'r': '00111', '!': '00100', 't': '0101', 'T': '00101'}
>>> c = encode(s,T)
>>> c
'1010010111001101110001011100001101001110101001100000110100000001111100101000100010100100'
>>> len(c)
88
>>> decode(c,T)
'Das ist ein kleiner Test!'
>>>
>>> s='im westen nichts neues'
>>> T=codetab(s)
>>> T
{' ': '001', 'c': '1001', 'e': '11', 'i': '101', 'h': '10000', 'm': '10001', 'n': '010',
's': '011', 'u': '00010', 't': '0000', 'w': '00011'}
>>> c=encode(s,T)
>>> c
'1011000100100011110110000110100010101011001100000000011001010110001011011'
>>> len(c)
73
>>> decode(c,T)
'im westen nichts neues'
>>>
Aufgabe
Das Verfahren ist auf Binär-Dateien auszubauen. Was ist da alles zu beachten?
